package com.tys.algorithm.bak.code1;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;

/**
 * 得奖系统规则：
 * 1如果某个用户购买商品数为0，又发生退货事件，认为该事件无效，得奖名单和之前事件一致
 * 2某用户发生购买商品事件，购买商品数+1，发生退货事件，购买商品数-1
 * 3.每次都是最多K个用户得奖，K也为传入的参数。
 * 如果根据全部规则，得奖数不够k个，就以不够的情况出结果
 * 4.得奖系统分为得奖区和候选区，任何用户只要购买数>0，一定在这两个区中的一个
 * 5.购买数量最大的前K名用户进入得奖区
 * 最初如果得奖区没有达K个用户，新来的直接进得奖区
 * 6.如果购买数不足以进入得奖区的用户，进入候选区
 * 7候选区购买数最多的用户，已经足以进入得奖区
 * 该用户替换得奖区中购买数最少的用户（大于才能替换）
 * 如果得奖区中购买数量最少用户有多个，替换最早进入得奖区的用户
 * 如果候选区中购买数量最多的用户有多个，机会给最早进入候选区的用户
 * 8.候选区和得奖区是两套时间
 * 用户只会在其中一个区域，只会有一个区域时间，另一个从得奖区出来进入候选区的用户，得奖区时间删除
 * 进入候选区的时间就是当前事件的时间，可以理解为arr[i]和top[i]中的i
 * 从候选区出来进入得奖区的用户，候选区时间删除
 * 进入得奖区的时间就是当前事件的时间
 * 9用户购买数==0，不管在哪个区都离开，区域时间删除，下次用户又发生购买行为，产生>0的购买数，根据之前规则回到某个区域中，进入时间重记
 * ​题目简化：
 * 1.用户购买数为0，发生退货，事件无效
 * 2.用户购买商品数+1，退货商品数-1
 * 3.<=K个用户得奖
 * 4.系统分得奖区和候选区，用户购买商品数>0
 * 5.得奖区：商品数最大的前k个数
 * 6.候选区：不满足得奖区的用户,
 * 7.候选区用户进入得奖区规则：
 * 多个用户时，看进入时间，机会给最早的
 * 8.候选区和得奖区两个时间
 * 从某个区进入另一个区，老时间删除，设置新时间
 * 9.用户购买数为0时，清空区域时间，下次重新计时和计数
 */
public class Code34_EveryStepShowBoss {
    //顾客类
    public static class Customer {
        public int id;//顾客id
        public int buy;//购买数量
        public int enterTime;//进入区时间

        public Customer(int v, int b, int o) {
            id = v;
            buy = b;
            enterTime = 0;
        }

        //候选区比较器：买的多的，进入时间早的排前面，好的在前
        public static class CandidateComparator implements Comparator<Customer> {

            @Override
            public int compare(Customer o1, Customer o2) {
                return o1.buy != o2.buy ? (o2.buy - o1.buy) : (o1.enterTime - o2.enterTime);
            }
        }

        //得奖区：买的少的，进入时间早的排前面，差的在前
        public static class DaddyComparator implements Comparator<Customer> {

            @Override
            public int compare(Customer o1, Customer o2) {
                return o1.buy != o2.buy ? (o1.buy - o2.buy) : (o1.enterTime - o2.enterTime);
            }
        }


        /**
         * 方法1：暴力法
         * 干完所有事，模拟不优化
         *
         * @param arr 顾客数组
         * @param op  对应顾客买还是卖
         * @param k   最大获奖人数
         * @return
         */
        public static List<List<Integer>> compare(int[] arr, boolean[] op, int k) {
            //顾客存储表
            HashMap<Integer, Customer> map = new HashMap<>();
            //候选区
            ArrayList<Customer> cands = new ArrayList<>();
            //得奖区
            ArrayList<Customer> daddy = new ArrayList<>();
            //获奖名单
            List<List<Integer>> ans = new ArrayList<>();

            //循环顾客数组
            for (int i = 0; i < arr.length; i++) {
                int id = arr[i]; //顾客id
                boolean buyOrRefund = op[i]; //买或卖
                //退货并且顾客表没有该顾客，获奖名单不变
                //顾客之前购买数=0，此时退货
                if (!buyOrRefund && !map.containsKey(id)) {
                    //得到获奖名单
                    ans.add(getCurAns(daddy));
                    //继续遍历
                    continue;
                }

                //顾客表中没有顾客
                //顾客之前购买数=0，此时买货
                //顾客之前购买数>0，此时买货
                //顾客之前购买数>0，此时退货
                if (!map.containsKey(id)) {
                    //新建用户
                    map.put(id, new Customer(id, 0, 0));
                }
                //买或卖
                Customer c = map.get(id);
                if (buyOrRefund) {
                    c.buy++; //买
                } else {
                    c.buy--; //卖
                }
                //删除顾客
                if (c.buy == 0) {
                    map.remove(id);
                }
                //顾客c
                //新来的用户刚买：候选区和得奖区都没有
                if (!cands.contains(c) && !daddy.contains(c)) {
                    //得奖区没满
                    if (daddy.size() < k) {
                        //设置时间
                        c.enterTime = i;
                        //直接加入得奖区
                        daddy.add(c);
                    } else {
                        //得奖区满了：加入候选区
                        c.enterTime = i;
                        cands.add(c);
                    }
                }
                //清理候选区中购买数为0的顾客
                cleanZeroBuy(cands);
                //清理得奖区中购买数为0的顾客
                cleanZeroBuy(daddy);
                //候选区排序
                cands.sort(new CandidateComparator());
                //得奖区排序
                daddy.sort(new DaddyComparator());
                //调整得奖区和候选区
                move(cands, daddy, k, i);
                //获取获奖名单
                ans.add(getCurAns(daddy));
            }
            return ans;
        }

        /**
         * 调整得奖区和候选区
         *
         * @param cands
         * @param daddy
         * @param k
         * @param time
         */
        public static void move(ArrayList<Customer> cands, ArrayList<Customer> daddy, int k, int time) {
            //候选区为空，不需要调整
            if (cands.isEmpty()) {
                return;
            }
            //候选区有顾客
            //得奖区没满
            if (daddy.size() < k) {
                //获得候选区排名第一的顾客
                Customer c = cands.get(0);
                //设置时间
                c.enterTime = time;
                //加入得奖区
                daddy.add(c);
                //从候选区删除
                cands.remove(0);
            } else {
                //得奖区满了
                //候选区排名第一购买数量 > 得奖区排名第一的数量，替换
                if (cands.get(0).buy > daddy.get(0).buy) {
                    //保存得奖区排名第一的顾客
                    Customer oldDaddy = daddy.get(0);
                    //从删除得奖区排名第一的顾客
                    daddy.remove(0);
                    //保存候选区排名第一的顾客
                    Customer newDaddy = cands.get(0);
                    //删除候选区排名第一的顾客
                    cands.remove(0);
                    //候选区顾客和得奖区顾客时间重置
                    newDaddy.enterTime = time;
                    oldDaddy.enterTime = time;
                    //候选区第一名加入得奖区
                    daddy.add(newDaddy);
                    //得奖区第一名加入候选区
                    cands.add(oldDaddy);
                }
            }
        }

        //清理数组中购买数量为0 的顾客
        public static void cleanZeroBuy(ArrayList<Customer> arr) {
            //临时存储购买数不为0的表
            List<Customer> noZero = new ArrayList<Customer>();
            //遍历数组找到购买数不为0 的顾客，加入临时数组
            for (Customer c : arr) {
                if (c.buy != 0) {
                    noZero.add(c);
                }
            }
            //清空原数组
            arr.clear();
            //将临时数组中数据拷贝到原数组
            for (Customer c : noZero) {
                arr.add(c);
            }
        }

        //得到获奖名单：将得奖区用户遍历出来
        public static List<Integer> getCurAns(ArrayList<Customer> daddy) {
            List<Integer> ans = new ArrayList<>();
            for (Customer c : daddy) {
                //加入获奖名单
                ans.add(c.id);
            }
            return ans;
        }

        /**
         * 方法2：使用堆，优化
         *
         * @param arr 顾客数组
         * @param op  对应顾客买还是卖
         * @param k   最大获奖人数
         * @return
         */
        public static List<List<Integer>> topK(int[] arr, boolean[] op, int k) {
            List<List<Integer>> ans = new ArrayList<>();
            WhosYourDaddy whoDaddies = new WhosYourDaddy(k);
            for (int i = 0; i < arr.length; i++) {
                whoDaddies.operate(i, arr[i], op[i]);
                ans.add(whoDaddies.getDaddies());
            }
            return ans;
        }


        //堆结构
        public static class WhosYourDaddy {
            //顾客表
            private HashMap<Integer, Customer> customers;
            //候选区加强堆
            private Code33_HeapGreater<Customer> candHeap;
            //得奖区加强堆
            private Code33_HeapGreater<Customer> daddyHeap;
            //得奖区大小限制
            private final int daddyLimit;

            //构造函数初始化
            public WhosYourDaddy(int limit) {
                customers = new HashMap<Integer, Customer>();
                //候选区大根堆：购买数多排上面，时间早排上面
                candHeap = new Code33_HeapGreater<>(new CandidateComparator());
                //得奖区小跟对：购买数少排上面，时间早排上面
                daddyHeap = new Code33_HeapGreater<>(new DaddyComparator());
                daddyLimit = limit;
            }

            /**
             * 当前处理 i 号事件， arr[i] -> 顾客id， buyOrRefund买或卖
             *
             * @param time        当前时间
             * @param id          顾客id
             * @param buyOrRefund 买还是卖
             */
            public void operate(int time, int id, boolean buyOrRefund) {
                //退货，顾客表中没有
                if (!buyOrRefund && !customers.containsKey(id)) {
                    return;
                }
                //新用户：顾客表中没有
                if (!customers.containsKey(id)) {
                    //新建顾客
                    customers.put(id, new Customer(id, 0, 0));
                }
                //得到顾客
                Customer c = customers.get(id);
                if (buyOrRefund) {
                    c.buy++; //买
                } else {
                    c.buy--; //卖
                }
                //购买数量为0，删除用户
                if (c.buy == 0) {
                    customers.remove(id);
                }

                //上面都是O(1)
                //下面优化：O(logN)

                //候选区和得奖区都没有顾客c
                if (!candHeap.contains(c) && !daddyHeap.contains(c)) {
                    //得奖区没满：直接加入得奖区
                    if (daddyHeap.size() < daddyLimit) {
                        c.enterTime = time;
                        daddyHeap.push(c);
                    } else {
                        //得奖区满了：加入候选区
                        c.enterTime = time;
                        candHeap.push(c);
                    }
                } else if (candHeap.contains(c)) {
                    //候选区中有顾客c
                    //购买数为0
                    if (c.buy == 0) {
                        //从候选区中删除顾客
                        candHeap.remove(c);
                    } else {
                        //重新调整候选区堆中c的位置
                        candHeap.resign(c);
                    }
                } else {
                    //得奖区中有顾客c
                    //购买数为0
                    if (c.buy == 0) {
                        //从得奖区删除顾客
                        daddyHeap.remove(c);
                    } else {
                        //重新调整得奖区堆中c的位置
                        daddyHeap.resign(c);
                    }
                }
                //调整得奖区和候选区的顾客
                daddyMove(time);
            }

            //得到获奖名单：得奖区所有用户遍历出来
            public List<Integer> getDaddies() {
                //得奖区所有顾客
                List<Customer> customers = daddyHeap.getAllElements();
                List<Integer> ans = new ArrayList<>();
                //全部加入获奖名单
                for (Customer c : customers) {
                    ans.add(c.id);
                }
                return ans;
            }

            //调整候选区和得奖区
            private void daddyMove(int time) {
                //候选区为空不需要调整
                if (candHeap.isEmpty()) {
                    return;
                }
                //得奖区没有满则直接加入得奖区
                if (daddyHeap.size() < daddyLimit) {
                    Customer p = candHeap.pop();
                    p.enterTime = time;
                    daddyHeap.push(p);
                } else {
                    //得奖区满了
                    //候选区中排名第一顾客购买数 > 得奖区中排名第一顾客购买数
                    if (candHeap.peek().buy > daddyHeap.peek().buy) {
                        //保存得奖区第一名顾客
                        Customer oldDaddy = daddyHeap.pop();
                        //保存候选区第一名顾客
                        Customer newDaddy = candHeap.pop();
                        //重置时间
                        oldDaddy.enterTime = time;
                        newDaddy.enterTime = time;
                        //交换顾客
                        daddyHeap.push(newDaddy);
                        candHeap.push(oldDaddy);
                    }
                }
            }
        }

        //--------------test----------------------
        //顾客购物类：存储顾客和顾客购买还是退货标记
        public static class Data {
            public int[] arr; //顾客数组
            public boolean[] op; //购买和退货标记数组

            public Data(int[] a, boolean[] o) {
                arr = a;
                op = o;
            }
        }

        //随机一个顾客购物类
        public static Data randomData(int maxValue, int maxLen) {
            int len = (int) (Math.random() * maxLen) + 1;
            int[] arr = new int[len];
            boolean[] op = new boolean[len];
            for (int i = 0; i < len; i++) {
                arr[i] = (int) (Math.random() * maxValue); //随机顾客id
                op[i] = Math.random() < 0.5 ? true : false; //随机是买还是退货
            }
            return new Data(arr, op);
        }

        //对比两个获奖名单是否相等
        public static boolean sameAnswer(List<List<Integer>> ans1, List<List<Integer>> ans2) {
            if (ans1.size() != ans2.size()) {
                return false;
            }
            for (int i = 0; i < ans1.size(); i++) {
                List<Integer> cur1 = ans1.get(i);
                List<Integer> cur2 = ans2.get(i);
                //长度不同则不相等
                if (cur1.size() != cur2.size()) {
                    return false;
                }
                //升序：从小到大排序
                cur1.sort((a, b) -> a - b);
                cur2.sort((a, b) -> a - b);
                //遍历数组
                for (int j = 0; j < cur1.size(); j++) {
                    if (!cur1.get(j).equals(cur2.get(j))) {
                        return false;
                    }
                }
            }
            return true;
        }

        public static void main(String[] args) {
            int maxValue = 10;
            int maxLen = 100;
            int maxK = 6;
            int testTimes = 10000;
            System.out.println("测试开始");
            for (int i = 0; i < testTimes; i++) {
                Data testData = randomData(maxValue, maxLen);
                int k = (int) (Math.random() * maxK) + 1;
                int[] arr = testData.arr;
                boolean[] op = testData.op;
                List<List<Integer>> ans1 = topK(arr, op, k);
                List<List<Integer>> ans2 = compare(arr, op, k);
                if (!sameAnswer(ans1, ans2)) {
                    for (int j = 0; j < arr.length; j++) {
                        System.out.println(arr[j] + ", " + op[j]);
                    }
                    System.out.println(k);
                    System.out.println(ans1);
                    System.out.println(ans2);
                    System.out.println("出错了");
                    break;
                }
            }
            System.out.println("测试结束");
        }

    }


}
